package com.cn.codebrush.练习;

import java.util.*;

public class Practice {
    public static void main(String[] args) {


    }


    // 5. 最长回文子串
    // s = "baabad"
    public String longestPalindrome(String s) {
        String res = "";
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s.charAt(i)==s.charAt(j) &&(j-i<2 || dp[i+1][j-1])){
                    dp[i][j] = true;
                    res = res.length()>s.substring(i,j+1).length()?res:s.substring(i,j+1);
                }
            }
        }

        return res;
    }


    //52
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        List<int[]> resList = new ArrayList<>();
        if (intervals.length == 0 || intervals == null) return resList.toArray(new int[0][]);
        Arrays.sort(intervals,(a,b) -> a[0] - b[0]);
        for(int i=0;i<n;i++){
            int left = intervals[i][0];
            int right = intervals[i][1];
            while(i<intervals.length-1 && intervals[i+1][0] <= right){
                i++;
                right = Math.max(right,intervals[i][1]);
            }
            resList.add(new int[]{left,right});
        }

        return resList.toArray(new int[0][]);
    }

    //背包
    public static int rob(int[] nums1, int[] nums2, int sum){
        int m = nums1.length;  //重量
        int n = nums2.length;  //价值
        int[][] dp = new int[m][sum+1];

        for(int i=0;i<m;i++){
            for(int j=sum;j>=0;j--){
                if(nums1[i] > j){
                    if(i == 0){
                        dp[i][j] = 0;
                    }else {
                        dp[i][j] = dp[i-1][j];
                    }

                }else {
                    if(i == 0){
                        dp[i][j] = 0;
                    }else {
                        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums1[i]]+nums2[i]);
                    }

                }
            }
        }

        return dp[m-1][sum];
    }


    //565. 数组嵌套
    public static int arrayNesting(int[] nums) {

            //dp[i]表示以i结尾的元素的嵌套最大长度
            int ret = 0;
            int len = nums.length;
            for(int i = 0; i < len; i++){
                if(nums[i] == -1) continue;
                int last_index, index = i, k = 0;
                while(nums[index] != -1){
                    last_index = index;
                    index = nums[index];
                    nums[last_index] = -1; // 将当前环上的元素设置为访问过
                    ++k;
                }
                ret = Math.max(ret, k);
            }
            return ret;


        /*int n = nums.length;
        int res = 0;
        for(int i=0;i<n;i++){
            int val = nums[i];
            Map<Integer,Integer> map = new HashMap();
            while(!map.containsKey(val)){
                map.put(val,nums[val]);
                val = nums[val];
            }
            res = Math.max(res,map.size());
        }

        return res;*/
    }




    /**
     * 5.最长回文串  abacca
     */
    public static String re(String s){
        int n = s.length();
        String res = "";
        boolean[][] dp = new boolean[n][n];
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s.charAt(i) == s.charAt(j) && (j-i<2 || dp[i+1][j-1])){
                    dp[i][j] = true;
                    res = res.length()>s.substring(i,j+1).length()?res:s.substring(i,j+1);
                }
            }
        }

        return res;
    }



    /**
     * 18. 四数之和
     * TODO 未完成
     */
    /**
     * [1000000000,1000000000,1000000000,1000000000]
     * -294967296
     * [1,-2,-5,-4,-3,3,3,5]
     * -11
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        List list = new ArrayList();
        for(int i=0;i<n-3;i++){
            if(i>0 && nums[i-1] == nums[i]){continue;}
            if(target<0 && nums[0] > 0){
                return list;
            }
            if(target>=0 && nums[n-1]<0){
                return list;
            }
            for(int j=i+1;j<nums.length;j++){
                if(j>i+1 && nums[j-1] == nums[j]){continue;}
                int left=j+1;
                int right = n-1;
                while(left < right){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum == target){
                        list.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left<right && nums[right]==nums[right-1]){right--;}
                        while(left<right && nums[left]==nums[left+1]){left++;}
                        left++;
                        right--;
                    }else if(sum > target){
                        right--;
                    }else{
                        left++;
                    }
                }
            }

        }

        return list;
    }

    /**
     * 15. 三数之和
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List list = new ArrayList();
        Arrays.sort(nums);
        for(int i=0;i<n-2;i++){
            if(i>0 && nums[i]==nums[i-1]){continue;}
            int left=i+1;
            int right = n-1;
            while(left<right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0){
                    list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left<right && nums[right]==nums[right-1]){right--;}
                    while(left<right && nums[left]==nums[left+1]){left++;}
                    right--;
                    left++;
                }else if(sum > 0){
                    right--;
                }else{
                    left++;
                }
            }
        }

        return list;
    }


    /**
     * 快速排序
     */
    public static int[] quickSort(int[] nums,int low,int high){
        if(low<high){
            int index = quickSortHelper(nums,low,high);
            quickSort(nums,0,index-1);
            quickSort(nums,index+1,high);
        }
        return nums;
    }
    public static int quickSortHelper(int[] nums,int low,int high){
        int index = nums[low];
        while (low<high){
            while(low<high && nums[high] >= index){
                high--;
            }
            nums[low] = nums[high];
            while (low<high && nums[low] <= index){
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = index;

        return low;
    }



    /**
     * 11. 盛最多水的容器
     * @param height
     * @return
     */
    public static int maxArea(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n-1;
        int res = 0;
        while (left<right){
            res = Math.max(res,(Math.min(height[left],height[right])*(right - left)));
            if(height[left] >= height[right]){
                right--;
            }else {
                left++;
            }
        }
        return res;
    }

    /**
     * 31. 下一个排列
     * 4 5 1 3 2
     * 4 5 2 1 3
     * @param nums
     */
    public static void nextPermutation(int[] nums) {
        int n = nums.length;
        int cut =0;
        for(int i=n-1;i>0;i--){
            if(nums[i] > nums[i-1]){
                cut = i;
                break;
            }
        }

        if(cut == 0){
            Arrays.sort(nums);
        }else {
            Arrays.sort(nums,cut,n);
            for(int j=cut;j<n;j++){
                if(nums[j] > nums[cut-1]){
                    int temp = nums[cut-1];
                    nums[cut-1] = nums[j];
                    nums[j] = temp;
                    break;
                }
            }
        }

    }
}
